package algotithm.leetcode.dp.test120;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 25068
 * @Date 2021/4/28 22:55
 * @Title 120. 三角形最小路径和
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] ans = {{2},{3,4},{6,5,7},{4,1,8,3}};
        List<List<Integer>> triangle = new ArrayList<>();
        for (int i = 0; i < ans.length; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < ans[i].length; j++) {
                list.add(ans[i][j]);
            }
            triangle.add(list);
        }
        int minimumTotal = solution.minimumTotal(triangle);
        System.out.println(minimumTotal);
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] f = new int[n];
        f[0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            f[i] = f[i - 1] + triangle.get(i).get(i);
            for (int j = i - 1; j > 0; --j) {
                f[j] = Math.min(f[j - 1], f[j]) + triangle.get(i).get(j);
            }
            f[0] += triangle.get(i).get(0);
        }
        int minTotal = f[0];
        for (int i = 1; i < n; ++i) {
            minTotal = Math.min(minTotal, f[i]);
        }
        return minTotal;
    }
}
